/*
 * @lc app=leetcode.cn id=30 lang=java
 *
 * [30] 串联所有单词的子串
 */

import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
// @lc code=start
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {

        List<Integer> res = new ArrayList<Integer>();

        int m = words.length;
        int n=words[0].length();
        int ls = s.length();

        for (int i = 0; i < n; i++) {

            if (i + m * n > ls) {
                //超长了
                break;
            }

            // 存放s中所有单词的子串及其次数
            Map<String, Integer> differ = new HashMap<>();
            for (int j = 0; j < m;j++) {
                String word = s.substring(i+j*n, i+(j+1)*n);
                differ.put(word,differ.getOrDefault(word, 0) + 1);
            }

            // 检索word中的子串是否在s中
            for (String word : words) {
                differ.put(word,differ.getOrDefault(word, 0) - 1);
                if(differ.get(word) == 0) {
                    differ.remove(word);
                }
            }

            for (int start = i;start < ls - m*n + 1; start += n) {
                if (start != i) {
                    String word = s.substring(start + (m-1) * n, start + m * n);
                    differ.put(word, differ.getOrDefault(word, 0) + 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                    word = s.substring(start - n, start);
                    differ.put(word, differ.getOrDefault(word, 0) - 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                }

                if (differ.isEmpty()) {
                    res.add(start);
                }

            }

        }
        return res;
    }
}
// @lc code=end

